﻿// 1002train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <numeric>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>

using namespace std;

/*
 相对开音节构成的结构为辅音+元音（aeiou）+辅音(r除外)+e，
 常见的单词有bike、cake等。
给定一个字符串，以空格为分隔符，反转每个单词中的字母，
若单词中包含如数字等其他非字母时不进行反转。
反转后计算其中含有相对开音节结构的子串个数（连续的子串中部分字符可以重复）。

输入描述
字符串，以空格分割的多个单词，字符串长度<10000，字母只考虑小写

输出描述
含有相对开音节结构的子串个数

输入
ekam a ekac
输出
2
反转后为 make a cake 其中make、cake为相对开音节子串，返回2
 */
class Solution01
{
public:
    bool checkVerify(string&str)
    {
        for (auto&ch:str)
        {
            //若单词中包含如数字等其他非字母
            bool is_small = ch >= 'a' && ch <= 'z';
            bool is_big = ch >= 'A' && ch <= 'Z';
            if (!is_small && !is_big) return false;
        }
        return true;
    }

    bool checkStruct(string&origin_sub)
    {
        string sub_str;
        for (auto&ch: origin_sub)
        {
            sub_str += tolower(ch);
        }

        //辅音+元音（aeiou）+辅音(r除外)+e
        unordered_set<char>aeiou_set = { 'a','e','i','o','u' };

        bool res0 = aeiou_set.count(sub_str[0]) == 0;
        bool res1 = aeiou_set.count(sub_str[1]) > 0;
        bool res2 = sub_str[2] != 'r' && aeiou_set.count(sub_str[2]) == 0;
        bool res3 = sub_str[3] == 'e';

        return res0 && res1 && res2 && res3;
        //checkStruct
    }

    int compute(string&str)
    {
        if (str.size() < 4) return 0;

        unordered_set<string>sub_set;
        int result = 0;
        int str_size = str.size();
        for (int left=0,right=3; right< str_size; left++,right++)
        {
            string sub_str = str.substr(left, 4);
            if (checkStruct(sub_str))
            {
                result++;
                track.push_back(sub_str);
            }
	        //for---
        }
        return result;
        //compute
    }

    Solution01(vector<string>&str_vec)
    {
	    //辅音+元音（aeiou）+辅音(r除外)+e
        //若单词中包含如数字等其他非字母时不进行反转
        //反转后计算其中含有相对开音节结构的子串个数
        int result = 0;
        for (auto&str:str_vec)
        {
            if (!checkVerify(str))
                continue;

            reverse(str.begin(), str.end());

            int count = compute(str);
            result += count;
            //for---
        }
        //for (auto&str:track)
        //{
        //    cout << str << ' ';
        //}
        cout << result;
        //Solution01
    }
private:
    vector<string>track;
};


/*
MVP 的条件是单场最高分得分获得者，可以并列。
所以宇宙战队决定在比赛中尽可能让更多队员上场，
并且让所有得分的选手得分都相同，然而比赛过程中的每一分钟的得分都只能由某一个人包揽。

输入描述
输入第一行为一个数字 t ，表示为有得分的分钟数
- 1 ≤ t ≤ 50
第二行为 t 个数字，代表每一分钟的得分 p
- 1 ≤ p ≤ 50

输出描述
输出有得分的队员都是 MVP 时，最少得 MVP 得分

输入
9
5 2 1 5 2 1 5 2 1
输出
6

一共 4 人得分，分别都是 6 分
5 + 1 ， 5 + 1 ， 5 + 1 ， 2 + 2 + 2
 */
class Solution02
{
public:
    void backTrack(vector<int>& num_vec, int start, int split)
    {
        if (is_find) return;
        int v_size = num_vec.size();
        if (start == v_size)
        {
            for (auto&num:track)
            {
                if (num != target_sum_) return;
            }

            is_find = true;
            return;
        }

        for (int i=0; i<split; i++)
        {
            if (i > 0 && track[i] == track[i - 1])
                continue;

            track[i] += num_vec[start];

            if (track[i]<=target_sum_)
            {
                backTrack(num_vec, start + 1, split);
            }
            
            track[i] -= num_vec[start];
            //for---
        }


	    //backTrack
    }

    bool checkSplit(vector<int>& num_vec, int split)
    {
        if (sum_ % split != 0) return false;

    	target_sum_ = sum_ / split;
        track = vector<int>(split, 0);

        int max_num = *max_element(num_vec.begin(), num_vec.end());
        if (max_num > target_sum_) return false;

        int v_size = num_vec.size();

        backTrack(num_vec, 0, split);

        if (is_find) return true;
        //checkSplit
    }

    Solution02(vector<int>&num_vec)
    {
        sum_ = accumulate(num_vec.begin(), num_vec.end(), 0);
        sort(num_vec.rbegin(), num_vec.rend());

        int v_size = num_vec.size();
        for (int split= v_size; split>=2; split--)
        {
            checkSplit(num_vec, split);
            if (is_find) break;
        }
        if (!is_find)
        {
            cout << sum_;
            return;
        }
        cout << target_sum_;
	    //Solution02
    }
private:
    bool is_find = false;
    int target_sum_ = 0;
    int sum_ = 0;
    vector<int>track;
    
};




int main()
{
	{
        int v_size;
        cin >> v_size;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution02 solu(num_vec);

        return 0;
	}
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    vector<string>str_vec;
    while (oh_sstream>>token)
    {
        str_vec.push_back(token);
    }
    Solution01 solu(str_vec);
    return 0;

    //
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
